package leetcode.other.dynamic_programming;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/7/6 18:24
 */
public class 最长公共子串 {
    public static void main(String[] args) {
        System.out.println(new 最长公共子串().lcs("BABCA", "ABCBA"));
    }

    // 一维数组
    public int lcs(String str1, String str2) {
        if (str1 == null || str2 == null) return 0;
        char[] chars1 = str1.toCharArray();
        if (chars1.length == 0) return 0;
        char[] chars2 = str2.toCharArray();
        if (chars2.length == 0) return 0;

        // 列比较短在内侧，一维数组会短一些
        char[] rowStr = chars1, colStr = chars2;
        if (chars1.length < chars2.length) {
            rowStr = chars2;
            colStr = chars1;
        }

        int[] dp = new int[colStr.length + 1];
        int max = 0;
        for (int i = 1; i <= rowStr.length; i++) {
            // 存储 相对于 i,j 的左上角的值，即 dp[i-1][j-1]
            int cur = 0;
            for (int j = 1; j <= colStr.length; j++) {
                // 存储 相对于 i,j 的左上角的值，即 dp[i-1][j-1]
                int leftTop = cur;
                cur = dp[j];
                if (rowStr[i - 1] != colStr[j - 1]) {
                    // 重置0，不然会干扰下一个 i 循环的结果
                    dp[j] = 0;
                } else {
                    dp[j] = leftTop + 1;
                    max = Math.max(max, dp[j]);
                }
            }
        }
        return max;
    }

    // 二维数组
    public int lcs1(String str1, String str2) {
        if (str1 == null || str2 == null) return 0;
        char[] chars1 = str1.toCharArray();
        if (chars1.length == 0) return 0;
        char[] chars2 = str2.toCharArray();
        if (chars2.length == 0) return 0;

        int[][] dp = new int[chars1.length + 1][chars2.length + 1];
        int max = 0;
        for (int i = 1; i <= chars1.length; i++) {
            for (int j = 1; j <= chars2.length; j++) {
                if (chars1[i - 1] != chars2[j - 1]) continue;
                dp[i][j] = dp[i - 1][j - 1] + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
}
